from typing import List


class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        ans = min(abs(num - target) for num in arr)

        old_box = [arr]
        while old_box:
            new_box = []
            for old_lst in old_box:
                new_lst = []
                for i in range(len(old_lst) - 1):
                    num = old_lst[i] & old_lst[i + 1]
                    ans = min(ans, abs(num - target))
                    if not new_lst or num != new_lst[-1]:
                        new_lst.append(num)
                if new_lst:
                    new_box.append(new_lst)
            old_box = new_box

        return ans


if __name__ == "__main__":
    print(Solution().closestToTarget(arr=[9, 12, 3, 7, 15], target=5))  # 2
    print(Solution().closestToTarget(arr=[1000000, 1000000, 1000000], target=1))  # 999999
